/*
--------------------------------------------------------------------------------
				Ak-Lib. 
			 Project       	: Ak-Lib
			 Group         	: Ak-Lib R&D Team
			 Author        	: Ocean.Wang
			 Create Date 	: 05-01-2010
--------------------------------------------------------------------------------
Code Name 	:  A.K 	~v~
Description	:  Yet Another Cross-Platform Lib.
Cautions    	:
--------------------------------------------------------------------------------
Change History:
Version		: 0.1
Building 		: 05/01/10
10-05.01 first draft, build, debug and test.
--------------------------------------------------------------------------------
*/

#include "ak_zip.h"

// QuickLZ data compression library
// Copyright (C) 2006-2007 Lasse Mikkel Reinhold
// lar@quicklz.com
//
// QuickLZ can be used for free under the GPL-1 or GPL-2 license (where anything 
// released into public must be open source) or under a commercial license if such 
// has been acquired (see http://www.quicklz.com/order.html). The commercial license 
// does not cover derived or ported versions created by third parties under GPL.

// Public functions of QuickLZ


/* Under 64-bit Mode, the Decode Speed is 2X compare to 32-bit Mode ! */
#define	QLZ_X86_64
#ifdef 	QLZ_X86_64
#define QLZ_FAST_RW
#endif
#define QLZ_HASH_AND 			1
#define QLZ_HASH_ENTRIES 		4096
#define QLZ_HASH_SIZE 			(QLZ_HASH_AND + 1)*QLZ_HASH_ENTRIES*sizeof(unsigned char *)
#define QLZ_SCRATCH_COMP 		(QLZ_HASH_SIZE) + 16
#define QLZ_SCRATCH_DECOMP  	16
#define QLZ_EXTRA 				512

#if 1
static 	__inline unsigned int _qlz_hash(unsigned int i)
{
	return ((i >> 12) ^ i) & 0x0fff;
}
#else
#define QLZ_HASH_ENTRIES 		256
static 	__inline unsigned int _qlz_hash(unsigned int i)
{
	return ((i >> 8) ^ i) & 0x00ff;
}
#endif

#ifndef QLZ_FAST_RW
static 	__inline unsigned int _qlz_read(void  *src, unsigned int bytes)
{
#ifndef QLZ_X86_64
	unsigned char *p = (unsigned char*)src;
	switch (bytes){
		case 4:
			return(*p | *(p + 1) << 8 | *(p + 2) << 16 | *(p + 3) << 24);
		case 3: 
			return(*p | *(p + 1) << 8 | *(p + 2) << 16);
		case 2:
			return(*p | *(p + 1) << 8);
		case 1: 
			return(*p);
	}
	return 0;
#else
	/* As we only used the 1, 2, 3, 4*/
	return *((unsigned int*)src);
	#if 0
	if (bytes >= 1 && bytes <= 4)
		return *((unsigned int*)src);
	else
		return 0;
	#endif
#endif
}

static 	__inline 	void 	_qlz_write(unsigned int f, void *dst, unsigned int bytes)
{
#ifndef QLZ_X86_64
	unsigned char *p = (unsigned char*)dst;

	switch (bytes){
		case 4: 
			*p = (unsigned char)f;
			*(p + 1) = (unsigned char)(f >> 8);
			*(p + 2) = (unsigned char)(f >> 16);
			*(p + 3) = (unsigned char)(f >> 24);
			return;
		case 3:
			*p = (unsigned char)f;
			*(p + 1) = (unsigned char)(f >> 8);
			*(p + 2) = (unsigned char)(f >> 16);
			return;
		case 2:
			*p = (unsigned char)f;
			*(p + 1) = (unsigned char)(f >> 8);
			return;
		case 1:
			*p = (unsigned char)f;
			return;
	}
#else
	/* As we only used the 4,3,2*/
	*((unsigned int*)dst) = f;
	return;

	#if 0
	switch (bytes){
		case 4: 
		case 3:
		case 2:
			*((unsigned int*)dst) = f;
			return;
		case 1:
			*((unsigned char*)dst) = (unsigned char)f;
			return;
	}
	#endif
#endif
}

#else
#define _qlz_read(src, bytes) 			(*((unsigned int*)(src)))
#define _qlz_write(val, dst, bytes)		(*((unsigned int*)(dst)) = (unsigned int)(val))
#endif

static 	__inline 	void _qlz_memmove(unsigned char *dst, unsigned char *src, unsigned int n)
{
	/* cannot be replaced by overlap handling of memmove() due to LZSS algorithm */
#ifndef QLZ_X86_64

	if(n > 8 && src + n < dst){
		SYS_MEMCPY(dst, src, n);
	}
	else{
		unsigned char *end = dst + n;
		while(dst < end){
			*dst = *src;
			dst++;
			src++;
		}
	}
#else
	if (n < 5){
		*((unsigned int*)dst) = *((unsigned int*)src);
	}
	else{
		#if 0
		unsigned char *end = dst + n;
		while(dst < end){
			*((unsigned int*)dst) = *((unsigned int*)src);
			dst = dst + 4;
			src = src + 4;
		}
		#endif
		
		#if 1
		int nX;
		nX = (n + 3)/4;
		do{
			*((unsigned int*)dst) = *((unsigned int*)src);
			dst = dst + 4;
			src = src + 4;
		}while(--nX);
		#endif
	}
#endif
}


static 	__inline size_t 	_qlz_decomp_size(unsigned char *pSrc)
{
	unsigned int n, r;
	n = (((*pSrc) & 2) == 2) ? 4 : 1;
	r = _qlz_read(pSrc + 1 + n, n);
	r = r & (0xffffffff >> ((4 - n)*8));
	return r;
}

static 	__inline size_t 	_qlz_comp_size(unsigned char *pSrc)
{
	unsigned int n, r;
	n = (((*pSrc) & 2) == 2) ? 4 : 1;
	r = _qlz_read(pSrc + 1, n);
	r = r & (0xffffffff >> ((4 - n)*8));
	return r;
}


static 	unsigned int 	_qlz_comp_core(void *pSrc, unsigned char *pDst, 	unsigned int size,  
									unsigned char *hashtable[][QLZ_HASH_AND + 1], 
									unsigned char *first)
{
	unsigned char *	cSrc 	= (unsigned char*)pSrc;
	unsigned char *	cDst 	= pDst;
	unsigned char *	src 	= cSrc;
	unsigned char *	dst 	= cDst + 4;
	unsigned char *	pCWord 	= cDst;
	unsigned int 	vCWord 	= 1U << 31;
	unsigned char *	last 	= cSrc + size - 1;
	unsigned char *	guarant = last - 8;

	// save first 4 bytes uncompressed
	while((src < cSrc + 4) && (src < guarant)){
		vCWord = (vCWord >> 1);
		*dst = *src;
		dst++;
		src++;
	}
	
	while(src < guarant){
		unsigned int fetch;
		if ((vCWord & 1) == 1){
			// check if destinationc pointer could exceed pDst buffer
			if (dst > cDst + size){
				return 0;
			}
					
			// store control word
			_qlz_write((vCWord >> 1) | (1U << 31), pCWord, 4);
			pCWord = dst;
			dst += 4;
			vCWord = 1U << 31;

		}
		{
			unsigned char *o;
			unsigned int hash, matchlen, cached;

			fetch 	= _qlz_read(src, 4);
			hash 	= _qlz_hash(fetch);

			cached = fetch ^ *((unsigned int*)&(hashtable[hash][0]));
			*((unsigned int*)&(hashtable[hash][0])) = fetch;

			o = hashtable[hash][1];
			hashtable[hash][1] = src;
			if ((cached & 0xffffff) == 0 && (o > first) && (o < src - 3) && 
				((_qlz_read(o, 3) ^ _qlz_read(src, 3)) & 0xffffff) == 0 && 
				(src - o < 131071)){
				unsigned int f, offset;
				offset = (unsigned int)(src - o);
				if (cached & 0xffffffff){
					if(offset <= 63){
						// encode lz match
						*dst = (unsigned char)(offset << 2);
						vCWord = (vCWord >> 1) | (1U << 31);
						src += 3;
						dst++;
					}
					else if (offset <= 16383){
						// encode lz match
						f = (offset << 2) | 1;
						_qlz_write(f, dst, 2);
						vCWord = (vCWord >> 1) | (1U << 31);
						src += 3;
						dst += 2;
					}
					else{
						// encode literal
						*dst = *src;
						src++;
						dst++;
						vCWord = (vCWord >> 1);
					}
				}
				
				else{
					// encode lz match
					unsigned char *old_src = src;

					offset = (unsigned int)(src - o);
					vCWord = (vCWord >> 1) | (1U << 31);
					src += 3;
					while((*(o + (src - old_src)) == *src) && (src < guarant)){
						src++;
					}
					matchlen = (unsigned int)(src - old_src);
					
					if (matchlen <= 18 && offset <= 1023){
						f 	= ((matchlen - 3) << 2) | (offset << 6) | 2;
						_qlz_write(f, dst, 2);
						dst += 2;
					}

					else if(matchlen <= 34 && offset <= 65535){
						f 	= ((matchlen - 3) << 3) | (offset << 8) | 3;
						_qlz_write(f, dst, 3);
						dst += 3;
					}
					
					else if (matchlen >= 3){
						if (matchlen <= 2050){
							f = ((matchlen - 3) << 4) | (offset << 15) | 7;
							_qlz_write(f, dst, 4);
							dst += 4;
						}
						else{
							_qlz_write(7, 			dst, 4);
							_qlz_write(matchlen, 		dst + 4, 4);
							_qlz_write(offset, 		dst + 8, 4);
							dst += 12;							
						} 
					}
				}
			}
			
			else{
				// encode literal
				*dst = *src;
				src++;
				dst++;
				vCWord = (vCWord >> 1);
			}
		}
	}

	// save last pSrc bytes as literals
	while (src <= last){
		if ((vCWord & 1) == 1){
			_qlz_write((vCWord >> 1) | (1U << 31), pCWord, 4);
			pCWord = dst;
			dst += 4;
			vCWord = 1U << 31;
		}

		#if 0
		unsigned int vRead, hRead;
		if ((src < last - 2) && (src > cSrc + 3)){	
			vRead = _qlz_read(src, 4);
			hRead = _qlz_hash(vRead);
			hashtable[hRead][1] = src;
			*((unsigned int*)&(hashtable[hRead][0])) = vRead;
		}
		#endif
		
		*dst = *src;
		src++;
		dst++;

		vCWord = (vCWord >> 1);
	}

	while((vCWord & 1) != 1){
		vCWord = (vCWord >> 1);
	}

	_qlz_write((vCWord >> 1) | (1U << 31), pCWord, 4);

	// min. size must be 9 bytes so that the qlz_size functions can take 9 bytes as argument
	if (dst - cDst < 9){
		return 9;
	}

	return (unsigned int)(dst - cDst);
}

static 	size_t 	_qlz_decomp_core(unsigned char *pSrc, void *pDst, 
									size_t size)
{
	unsigned char 	* cSrc 	= pSrc;
	unsigned char 	* cDst	= (unsigned char*)pDst;
	unsigned char 	* src	= cSrc;
	unsigned char 	* dst 	= cDst;
	unsigned char	* last 	= cDst + size;
	unsigned char 	* guarant 	= last - 4;
	unsigned int 	vCWord 		= 1;
	unsigned int 	bitlut[16] 	= {4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
		
	// prevent spurious memory read on a pSrc with size < 4
	if (dst >= guarant){
		src += 4;
		while(dst < last){
			*dst = *src;
			dst++;
			src++;
		}

		return (unsigned int)(dst - cDst);
	}


	for(;;) {
		unsigned int fetch;

		if (vCWord == 1){
			// fetch control word
			vCWord = _qlz_read(src, 4) | (1U << 31);
			src += 4;
		}
		
		fetch = _qlz_read(src, 4);

	 	// check if we must decode lz match
		if ((vCWord & 1) == 1){
			unsigned int matchlen, offset;

			vCWord = vCWord >> 1;			

			if ((fetch & 3) == 0){
				offset = (fetch & 0xff) >> 2;
				_qlz_memmove(dst, dst - offset, 3);
				dst += 3;
				src++;
			}
			else if ((fetch & 2) == 0){
				offset = (fetch & 0xffff) >> 2;
				_qlz_memmove(dst, dst - offset, 3);
				dst += 3;
				src += 2;
			}
			else if ((fetch & 1) == 0)
			{
				offset = (fetch & 0xffff) >> 6;
				matchlen = ((fetch >> 2) & 15) + 3;
				_qlz_memmove(dst, dst - offset, matchlen);
				src += 2;
				dst += matchlen;
			}
			else if ((fetch & 4) == 0){
				offset = (fetch & 0xffffff) >> 8;
				matchlen = ((fetch >> 3) & 31) + 3;
				_qlz_memmove(dst, dst - offset, matchlen);
				src += 3;
				dst += matchlen;
			}
			else if ((fetch & 8) == 0){
				offset = (fetch >> 15);
				if (offset != 0){
					matchlen = ((fetch >> 4) & 2047) + 3;
					src += 4;
				}
				else{
					matchlen= _qlz_read(src + 4, 4);
					offset 	= _qlz_read(src + 8, 4);
					src += 12;
				}
				_qlz_memmove(dst, dst - offset, matchlen);
				dst += matchlen;
			}
			else{
				// decode rle sequence
				unsigned char rle_char;
				rle_char = (unsigned char)(fetch >> 16);
				matchlen = ((fetch >> 4) & 0xfff);

				if(matchlen != 0)
					src += 3;
				else
				{
					matchlen = _qlz_read(src + 3, 4);
					src += 7;
				}

				SYS_MEMSET(dst, rle_char, matchlen);
				dst += matchlen; 
			}
		}
		
		else{
			// decode literal
			_qlz_memmove(dst, src, 4);

			dst += bitlut[vCWord & 0xf];
			src += bitlut[vCWord & 0xf];
			vCWord = vCWord >> (bitlut[vCWord & 0xf]);

			if (dst >= guarant){
				// decode last literals and exit				
				while(dst < last){
					if (vCWord == 1){
						src += 4;
						vCWord = 1U << 31;
					}
					if (1 > cDst + size - dst)
						return 0;

					*dst = *src;
					dst++;
					src++;
					vCWord = vCWord >> 1;
				}

				if((src - 1) - cSrc > 8) // 8 bytes comp. size excessive len is ok
					return 0;
				else if(dst - cDst - size == 0)
					return size;
				else
					return 0;
			}
		}
	}
}


static 	size_t 		_qlz_compress( void *pSrc, char *pDst, size_t size, char *scratch)
{
	/* 1-8 bytes for aligning (not 0-7!); 8 bytes for buffersize (padds on 32 bit cpu); */
	unsigned char 		* bufferalign 	= (unsigned char *)scratch + 8 - (((size_t)scratch) % 8);
	size_t 				* buffersize 	= (size_t *)bufferalign;
	unsigned char *(*hashtable)[QLZ_HASH_AND + 1] = 
	(unsigned char *(*)[QLZ_HASH_AND + 1])(bufferalign + 8);
	
	unsigned int r, compressed, base;
	#if 0
	unsigned char 		* streambuffer 	= bufferalign + 8 + QLZ_HASH_SIZE;
	unsigned char 		* hashcounter 	= streambuffer;
	#endif

	if(size == 0 || size > 0xffffffff)
		return 0;

	if(size < 216)
		base = 3;
	else
		base = 9;

		r = base + _qlz_comp_core(	pSrc, (unsigned char*)pDst + base, (unsigned int)size, 
									hashtable, (unsigned char*)pSrc);
		if(r == base){
			SYS_MEMCPY(pDst + base, pSrc, size);
			r = (unsigned int)size + base;
			compressed = 0;
		}
		else{
			compressed = 1;
		}
		*buffersize = 0;
	
	if(base == 3){
		*pDst = (unsigned char)(0 | compressed);
		*(pDst + 1) = (unsigned char)r;
		*(pDst + 2) = (unsigned char)size;
	}
	else{
		*pDst = (unsigned char)(2 | compressed);
		_qlz_write(r, pDst + 1, 4);
		_qlz_write((unsigned int)size, pDst + 5, 4);
	}

	return (size_t)r;
}


static 	size_t 		_qlz_decompress(unsigned char *pSrc, void *pDst, size_t dstLen)
{
	/* 1-8 bytes for aligning (not 0-7!); 8 bytes for buffersize (padds on 32bit cpu); */
	unsigned int 		  headerlen 	= 2*((((*pSrc) & 2) == 2) ? 4 : 1) + 1; // get header len

	size_t dsiz = _qlz_decomp_size(pSrc);
	#if 0
	size_t csiz = _qlz_comp_size((char *)pSrc);
	#endif

	/* Judge if Buffer Avail */
	if(dsiz > dstLen)
		return 0;
	
	if((*pSrc & 1) == 1)		
		_qlz_decomp_core(pSrc + headerlen, pDst, dsiz);
	else
		SYS_MEMCPY(pDst, pSrc + headerlen, dsiz);

	return dsiz;
}


/* We Should Make Sure the Original Data is Not >  1M */
size_t 		_Qlz_Compress(unsigned char *pSrc, void *pDst, size_t srclen)
{
	char 	scratch[QLZ_SCRATCH_COMP];
	return 	_qlz_compress(pSrc, pDst, srclen, scratch);
}

size_t 		_Qlz_Decompress(unsigned   char *pSrc, void *pDst, size_t dstLen)
{
	#if 0
	char 	scratch[QLZ_SCRATCH_DECOMP];
	#endif
	return 	_qlz_decompress(pSrc, pDst, dstLen);
}

